def block_search(arr, block_size, target):
    """
    分块查找算法，若块内数据量较大且有序，可在块内也使用二分查找。
    参数：
        arr: 待查找的列表（分块有序）
        block_size: 每块的大小
        target: 目标值
    返回：
        找到目标值的索引（或-1表示未找到）
    """
    if not arr or block_size <= 0:
        return -1

    # 构建索引表：存储每块的最大值和起始索引
    index_table = []
    n = len(arr)
    for i in range(0, n, block_size):
        block_end = min(i + block_size - 1, n - 1)  # 块的结束索引
        max_val = max(arr[i:block_end + 1])  # 块内最大值
        index_table.append((max_val, i))  # (最大值, 块起始索引)

    # 第一步：在索引表中查找目标块，索引表按 “块内最大值” 排序
    # 若目标≤块最大值 且 目标 > 前一块最大值，则目标在当前块
    block_index = -1
    for i, (max_val, start_idx) in enumerate(index_table):
        if target <= max_val:
            block_index = i
            break
    if block_index == -1:
        return -1  # 目标值大于所有块的最大值，未找到

    # 第二步：在目标块内顺序查找
    start_idx = index_table[block_index][1]
    end_idx = min(start_idx + block_size, n)
    for i in range(start_idx, end_idx):
        if arr[i] == target:
            return i  # 找到目标，返回索引
    return -1  # 未找到

# 示例用法
if __name__ == "__main__":
    # 测试数据（分块有序：每块最大值升序）
    data = [2, 5, 1, 8, 3, 7, 12, 10, 9, 15, 13, 18]
    # 假设分块为每3个元素一块：块1=[2,5,1]（max=5）, 块2=[8,3,7]（max=8）,
    # 块3=[12,10,9]（max=12）, 块4=[15,13,18]（max=18）
    block_size = 3
    target1 = 7
    target2 = 11

    # 测试查找目标值7
    result1 = block_search(data, block_size, target1)
    if result1 != -1:
        print(f"目标值 {target1} 在索引 {result1} 处找到")
    else:
        print(f"目标值 {target1} 未找到")

    # 测试查找目标值11
    result2 = block_search(data, block_size, target2)
    if result2 != -1:
        print(f"目标值 {target2} 在索引 {result2} 处找到")
    else:
        print(f"目标值 {target2} 未找到")